package com.googlecode.boliang.Q04;

import java.util.Stack;

public class SearchSumValuePath {
	
	private int value;
	private Stack<Integer> valueStack = new Stack<Integer>(); 
	private int sumValue; 
	
	public void doSearch(BTNode curNode, int value) {
		this.value = value;
		this.sumValue = 0; 
		doPreOrderTraversal(curNode); 
	}
	
	public void doPreOrderTraversal(BTNode curNode) {
		
		if (curNode == null) return;
		
		System.out.println(curNode.getNodeValue()); 
		valueStack.push(curNode.getNodeValue()); 
		sumValue = sumValue + curNode.getNodeValue(); 
		System.out.println("sumValue " + sumValue); 
		
		doPreOrderTraversal(curNode.getLeftChild()); 
		
		doPreOrderTraversal(curNode.getRightChild()); 
		
		if (curNode.getLeftChild() == null && curNode.getRightChild() == null && sumValue == value) {
			System.out.println("Got one path" + curNode.getNodeValue()); 
		}
		
		valueStack.pop(); 
		sumValue = sumValue - curNode.getNodeValue(); 
	}

}
